Dynamic Network Flows - Chapter 6: Full Information Dynamic Equilibria

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\sMid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\deriv}[2][]{\partial_{#1} #2} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\cexittime}[1][e]{A_{#1}} \newcommand{\network}{N} \newcommand{\tauPmin}{\tau_{p_{\min}}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

Theorem A.21: Given $C \subseteq L^p([a,b])^d$ non-empty, closed, bounded, convex and $\mathcal{A}: C \to L^q([a,b])^d$ weak-strong sequentially continuous. There always exists a solution $f \in C$ to \[\langle\mathcal{A}(f),g-f\rangle \coloneqq \sum_{i=1}^d\int_a^b\mathcal{A}_i(f)(\zeta)\big(g_i(\zeta)-f_i(\zeta)\big)\diff\zeta \geq 0 \text{ f.a. } g \in C\]

Lemma 4.4: For any $f^+_e: \IR \to \IRnn$ loc.-int. with $\supp(f^+_e) \subseteq \IRnn$ there exists a $f^-_e$ such that $(f^+_e,f^-_e)$ is a Vickrey flow.

Lemma 4.5: $(f^+_e,f^-_e)$ and $(g^+_e,g^-_e)$ two Vickrey flows with $f^+_e(\theta) = g^+_e(\theta)$ f.a.a. $\theta \leq T$. Then, $f^-_e(\theta) = g^-_e(\theta)$ f.a.a. $\theta \leq \cexittime(T)$.

Lemma 4.7: The (Vickrey-)edge loading mapping \[\Phi_e^T: \set{f^+_e \in L^2(\IR) \sMid \supp(f^+_e) \subseteq [0,T], f^+_e \geq 0} \to L^1_{\mathrm{loc}}(\IR), f^+_e \mapsto f^-_e \text{ s.th. } (f^+_e,f^-_e) \text{ is Vickrey flow}\] is sequentially weak-weak-continuous.

$(f_p) \in \Lambda(u) \coloneqq \Set{(f_p) \in L^1_{\mathrm{loc}}(\IR)^{\PathSet} \SMid f_p \geq 0, \sum_{p \in \PathSet}f_p = u}$ is dynamic equilibrium wrt $\Psi: \Lambda(u) \to C(\IR)^{\PathSet}$ if \[f_p(\theta) \gt 0 \implies \Psi_p(f)(\theta) \leq \Psi_q(f)(\theta) \text{ for all } p,q \in \PathSet \text{ and almost all } \theta \in \IR.\]

Theorem 6.3: $t$ reachable from $s$, $u \in L^p(\IR)$ with bounded support and $\Psi: \Lambda(u) \to L^q(\IR)^{\PathSet}$ weak-strong sequentially cont.
Theorem 6.3: Then, there exists a dynamic equilibrium wrt. $\Psi$.

Edge-based Vickrey flow $(f^+_e,f^-_e)$ is corresponding Vickrey flow to path-based flow $(f_p)$ if there exist $f^+_{p,i}, f^-_{p,i}: \IR \to \IRnn$ s.th.: \[f^+_{p,i}(\theta) = \begin{cases}f_p(\theta), &\text{ if } i=1\\f^-_{p,i-1}(\theta), &\text{ else}\end{cases} \quad\text{ and }\quad \int_0^\theta f^+_{p,i}(\zeta)\diff\zeta = \int_0^{\cexittime[p[i]](\theta)}f^-_{p,i}(\zeta)\diff\zeta\] as well as \[f^+_e = \sum_{p \in \PathSet: \exists i: e=p[j]}f^+_{p,j} \quad\text{ and }\quad f^-_e = \sum_{p \in \PathSet: \exists i: e=p[j]}f^-_{p,j}\] for all $p$, $i$, $e$ and almost all $\theta$.

Lemma 4.13: $\network$ with $\tau_e \gt 0$. Then, there exists a unique corresponding (edge-based) Vickrey flow for any path-based flow.